/**
 * 给定⼀个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输⼊: [1,2,3]
输出:
[
 [1,2,3],
 [1,3,2],
 [2,1,3],
 [2,3,1],
 [3,1,2],
 [3,2,1]
]
 * */
// 思路
// 回溯的基本思路清参考上⽅的回溯专题。
// 以 [1,2,3] 为例，我们的逻辑是：
// 先从 [1,2,3] 选取⼀个数。
// 然后继续从 [1,2,3] 选取⼀个数，并且这个数不能是已经选取过的数。
// 如何确保这个数不能是已经选取过的数？我们可以直接在已经选取的数字中线性查找，也
// 可以将已经选取的数字中放到 hashset 中，这样就可以在 的时间来判断是否已经被
// 选取了，只不过需要额外的空间。
// 重复这个过程直到选取的数字个数达到了 3。
// 代码
// Javascript Code:
function backtrack(list, tempList, nums) {
 if (tempList.length === nums.length) return list.push([...tempList]);
 for (let i = 0; i < nums.length; i++) {
 if (tempList.includes(nums[i])) continue;
 tempList.push(nums[i]);
 backtrack(list, tempList, nums);
 tempList.pop();
 }
}
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
 const list = [];
 backtrack(list, [], nums);
 return list;
};
// function permute(nums) {    
//     let res = [];
//     backtrack(nums, 0, res);
//     return res;
// }   

// function backtrack(nums, start, res) {
//     // 当最后达到临界值
//     if (start === nums.length - 1) { 
//         res.push([...nums]);
//         return;     
//     }           
//     //利用下标索引交换生成新的序列
//     for (let i = start; i < nums.length; i++) {       
//         //交换
//         swap(nums, start, i);
//         //递归
//         backtrack(nums, start + 1, res);
//         // 还原
//         swap(nums, start, i);           
//     }       
// }      
// //交换         
// function swap(nums, i, j) {         
//     const temp = nums[i];
//     nums[i] = nums[j];
//     nums[j] = temp;     
// }                       


// console.log(permute([1,2,3]))


